﻿// -------------------------------------------------------------------------
//    @FileName         :    TestNFShmHashMultiMapWithListAdvanced.h
//    @Author           :    gaoyi
//    @Date             :    2024-01-20
//    @Email			:    445267987@qq.com
//    @Module           :    TestNFShmHashMultiMapWithListAdvanced
//
// -------------------------------------------------------------------------

#pragma once

#include "NFComm/NFShmStl/NFShmHashMultiMapWithList.h"
#include <gtest/gtest.h>
#include <string>
#include <vector>
#include <set>
#include <algorithm>
#include <chrono>
#include <random>

/**
 * @file TestNFShmHashMultiMapWithListAdvanced.h
 * @brief NFShmHashMultiMapWithList 高级链表排序接口的单元测试
 * 
 * 本文件专门测试多重映射容器的以下高级接口：
 * 1. insert_list_sorted() - 按有序位置插入元素（允许重复键）
 * 2. emplace_list_sorted() - 原地构造并按有序位置插入
 * 3. emplace_hint_list_sorted() - 带提示的原地构造并按有序位置插入
 * 4. move_to_list_node_front() - 将节点移到链表前端
 * 5. move_to_list_node_back() - 将节点移到链表后端
 * 6. move_to_list_sorted() - 将节点移到正确的有序位置
 * 
 * 特别关注多重映射的特性：
 * - 相同键的多个值的处理
 * - 键相邻性的保持
 * - equal_range的有效性
 */

// 测试用的学生成绩记录
struct ExamRecord
{
    std::string subject;
    int score;
    std::string date;

    ExamRecord() : score(0) {}
    ExamRecord(const std::string& s, int sc, const std::string& d) : subject(s), score(sc), date(d) {}

    bool operator==(const ExamRecord& other) const
    {
        return subject == other.subject && score == other.score && date == other.date;
    }

    bool operator<(const ExamRecord& other) const
    {
        if (score != other.score) return score < other.score;
        if (subject != other.subject) return subject < other.subject;
        return date < other.date;
    }
};

/**
 * @brief 测试MultiMap的insert_list_sorted接口
 */
TEST(NFShmHashMultiMapWithListAdvancedTest, InsertListSorted)
{
    printf("========== MultiMap InsertListSorted Test ==========\n");

    NFShmHashMultiMapWithList<std::string, int, 100> studentScores;
    studentScores.CreateInit();

    // 测试1：使用默认比较器插入多个相同键的值
    printf("Test 1: Insert multiple values for same key with default comparator\n");
    
    auto it1 = studentScores.insert_list_sorted({"Alice", 85});
    EXPECT_EQ(it1->first, "Alice");
    EXPECT_EQ(it1->second, 85);

    auto it2 = studentScores.insert_list_sorted({"Alice", 92});
    EXPECT_EQ(it2->first, "Alice");
    EXPECT_EQ(it2->second, 92);

    auto it3 = studentScores.insert_list_sorted({"Alice", 78});
    EXPECT_EQ(it3->first, "Alice");
    EXPECT_EQ(it3->second, 78);

    auto it4 = studentScores.insert_list_sorted({"Bob", 89});
    EXPECT_EQ(it4->first, "Bob");
    EXPECT_EQ(it4->second, 89);

    auto it5 = studentScores.insert_list_sorted({"Bob", 91});
    EXPECT_EQ(it5->first, "Bob");
    EXPECT_EQ(it5->second, 91);

    printf("After insert_list_sorted (should be sorted by value):\n");
    std::vector<int> values;
    for (auto it = studentScores.list_begin(); it != studentScores.list_end(); ++it)
    {
        printf("  %s: %d\n", it->first.c_str(), it->second);
        values.push_back(it->second);
    }

    // 验证按value升序排列
    EXPECT_TRUE(std::is_sorted(values.begin(), values.end()));
    EXPECT_EQ(studentScores.size(), 5);
    EXPECT_EQ(studentScores.count("Alice"), 3);
    EXPECT_EQ(studentScores.count("Bob"), 2);

    // 验证equal_range仍然有效
    auto alice_range = studentScores.equal_range("Alice");
    int alice_count = 0;
    printf("\nAlice's scores via equal_range:\n");
    for (auto it = alice_range.first; it != alice_range.second; ++it)
    {
        printf("  Alice: %d\n", it->second);
        alice_count++;
    }
    EXPECT_EQ(alice_count, 3);

    studentScores.clear();

    // 测试2：使用自定义比较器（按value降序）
    printf("\nTest 2: Custom comparator (descending by value)\n");
    
    auto comp = [](const int& a, const int& b) { return a > b; };
    
    studentScores.insert_list_sorted({"Alice", 85}, comp);
    studentScores.insert_list_sorted({"Alice", 92}, comp);
    studentScores.insert_list_sorted({"Alice", 78}, comp);
    studentScores.insert_list_sorted({"Bob", 89}, comp);
    studentScores.insert_list_sorted({"Bob", 91}, comp);

    printf("After insert_list_sorted with descending comparator:\n");
    std::vector<int> desc_values;
    for (auto it = studentScores.list_begin(); it != studentScores.list_end(); ++it)
    {
        printf("  %s: %d\n", it->first.c_str(), it->second);
        desc_values.push_back(it->second);
    }

    // 验证按value降序排列
    EXPECT_TRUE(std::is_sorted(desc_values.begin(), desc_values.end(), std::greater<int>()));

    printf("MultiMap InsertListSorted test passed\n");
}

/**
 * @brief 测试MultiMap的emplace_list_sorted接口
 */
TEST(NFShmHashMultiMapWithListAdvancedTest, EmplaceListSorted)
{
    printf("========== MultiMap EmplaceListSorted Test ==========\n");

    NFShmHashMultiMapWithList<int, ExamRecord, 100> examResults;
    examResults.CreateInit();

    // 测试1：使用默认比较器原地构造多个记录
    printf("Test 1: Emplace multiple records with default comparator\n");
    
    auto it1 = examResults.emplace_list_sorted(1001, ExamRecord("Math", 85, "2024-01-15"));
    EXPECT_EQ(it1->first, 1001);
    EXPECT_EQ(it1->second.score, 85);

    auto it2 = examResults.emplace_list_sorted(1001, ExamRecord("Physics", 92, "2024-01-16"));
    EXPECT_EQ(it2->first, 1001);
    EXPECT_EQ(it2->second.score, 92);

    auto it3 = examResults.emplace_list_sorted(1001, ExamRecord("Chemistry", 78, "2024-01-17"));
    EXPECT_EQ(it3->first, 1001);
    EXPECT_EQ(it3->second.score, 78);

    auto it4 = examResults.emplace_list_sorted(1002, ExamRecord("Math", 89, "2024-01-15"));
    EXPECT_EQ(it4->first, 1002);
    EXPECT_EQ(it4->second.score, 89);

    printf("After emplace_list_sorted (should be sorted by ExamRecord.score):\n");
    std::vector<int> scores;
    for (auto it = examResults.list_begin(); it != examResults.list_end(); ++it)
    {
        printf("  Student %d: %s = %d (%s)\n", 
               it->first, it->second.subject.c_str(), it->second.score, it->second.date.c_str());
        scores.push_back(it->second.score);
    }

    // 验证按score升序排列
    EXPECT_TRUE(std::is_sorted(scores.begin(), scores.end()));
    EXPECT_EQ(examResults.size(), 4);
    EXPECT_EQ(examResults.count(1001), 3);
    EXPECT_EQ(examResults.count(1002), 1);

    examResults.clear();

    // 测试2：使用自定义比较器（按科目名称升序，科目相同按分数降序）
    printf("\nTest 2: Custom comparator (by subject asc, then score desc)\n");
    
    auto comp = [](const ExamRecord& a, const ExamRecord& b) {
        if (a.subject != b.subject) return a.subject < b.subject;
        return a.score > b.score;
    };

    examResults.emplace_list_sorted_comp(comp, 1001, ExamRecord("Math", 85, "2024-01-15"));
    examResults.emplace_list_sorted_comp(comp, 1001, ExamRecord("Physics", 92, "2024-01-16"));
    examResults.emplace_list_sorted_comp(comp, 1001, ExamRecord("Math", 78, "2024-01-17"));
    examResults.emplace_list_sorted_comp(comp, 1002, ExamRecord("Physics", 89, "2024-01-15"));
    examResults.emplace_list_sorted_comp(comp, 1002, ExamRecord("Chemistry", 94, "2024-01-18"));

    printf("After emplace_list_sorted with custom comparator:\n");
    for (auto it = examResults.list_begin(); it != examResults.list_end(); ++it)
    {
        printf("  Student %d: %s = %d (%s)\n", 
               it->first, it->second.subject.c_str(), it->second.score, it->second.date.c_str());
    }

    // 验证排序正确性：按科目分组，组内按分数降序
    std::string prev_subject = "";
    int prev_score = 100;
    for (auto it = examResults.list_begin(); it != examResults.list_end(); ++it)
    {
        if (!prev_subject.empty())
        {
            bool valid_order = (it->second.subject > prev_subject) || 
                              (it->second.subject == prev_subject && it->second.score <= prev_score);
            EXPECT_TRUE(valid_order);
        }
        prev_subject = it->second.subject;
        prev_score = (it->second.subject == prev_subject) ? it->second.score : 100;
    }

    printf("MultiMap EmplaceListSorted test passed\n");
}

/**
 * @brief 测试MultiMap的emplace_hint_list_sorted接口
 */
TEST(NFShmHashMultiMapWithListAdvancedTest, EmplaceHintListSorted)
{
    printf("========== MultiMap EmplaceHintListSorted Test ==========\n");

    NFShmHashMultiMapWithList<std::string, int, 100> categoryMap;
    categoryMap.CreateInit();

    // 测试：emplace_hint_list_sorted应该忽略hint参数，维持正确排序
    printf("Test: emplace_hint_list_sorted should maintain correct order\n");

    auto it1 = categoryMap.emplace_hint_list_sorted("Fruit", 80);
    EXPECT_EQ(it1->second, 80);

    auto it2 = categoryMap.emplace_hint_list_sorted("Fruit", 95);
    EXPECT_EQ(it2->second, 95);

    auto it3 = categoryMap.emplace_hint_list_sorted("Vegetable", 70);
    EXPECT_EQ(it3->second, 70);

    auto it4 = categoryMap.emplace_hint_list_sorted("Fruit", 85);
    EXPECT_EQ(it4->second, 85);

    auto it5 = categoryMap.emplace_hint_list_sorted("Meat", 120);
    EXPECT_EQ(it5->second, 120);

    printf("After emplace_hint_list_sorted:\n");
    std::vector<int> values;
    for (auto it = categoryMap.list_begin(); it != categoryMap.list_end(); ++it)
    {
        printf("  %s: %d\n", it->first.c_str(), it->second);
        values.push_back(it->second);
    }

    // 验证按value升序排列
    EXPECT_TRUE(std::is_sorted(values.begin(), values.end()));
    EXPECT_EQ(categoryMap.size(), 5);
    EXPECT_EQ(categoryMap.count("Fruit"), 3);

    // 验证equal_range仍然有效
    auto fruit_range = categoryMap.equal_range("Fruit");
    int fruit_count = 0;
    printf("\nFruit values via equal_range:\n");
    for (auto it = fruit_range.first; it != fruit_range.second; ++it)
    {
        printf("  Fruit: %d\n", it->second);
        fruit_count++;
    }
    EXPECT_EQ(fruit_count, 3);

    printf("MultiMap EmplaceHintListSorted test passed\n");
}

/**
 * @brief 测试MultiMap的move_to_list_node_front接口
 */
TEST(NFShmHashMultiMapWithListAdvancedTest, MoveToListNodeFront)
{
    printf("========== MultiMap MoveToListNodeFront Test ==========\n");

    NFShmHashMultiMapWithList<std::string, int, 100> scoreMap;
    scoreMap.CreateInit();

    // 插入多重数据并排序
    scoreMap.insert({"Alice", 85});
    scoreMap.insert({"Alice", 92});
    scoreMap.insert({"Bob", 78});
    scoreMap.insert({"Bob", 89});
    scoreMap.insert({"Charlie", 91});
    scoreMap.sort_list();  // 按value升序排序

    printf("Original sorted order:\n");
    for (auto it = scoreMap.list_begin(); it != scoreMap.list_end(); ++it)
    {
        printf("  %s: %d\n", it->first.c_str(), it->second);
    }

    // 测试1：移动某个特定的Alice记录到前端
    printf("\nTest 1: Move specific Alice record to front\n");
    
    auto alice_range = scoreMap.equal_range("Alice");
    auto target_alice = alice_range.first;
    ++target_alice;  // 指向Alice的第二个记录（92分）
    
    scoreMap.move_to_list_node_front(target_alice);

    printf("After moving Alice's second record to front:\n");
    std::vector<int> values_after_move;
    for (auto it = scoreMap.list_begin(); it != scoreMap.list_end(); ++it)
    {
        printf("  %s: %d\n", it->first.c_str(), it->second);
        values_after_move.push_back(it->second);
    }

    // 测试2：使用自定义比较器
    printf("\nTest 2: Move with custom comparator\n");
    
    auto comp = [](const int& a, const int& b) { return a > b; };
    auto bob_it = scoreMap.find("Bob");
    scoreMap.move_to_list_node_front(bob_it, comp);

    printf("After moving Bob to front with descending comparator:\n");
    for (auto it = scoreMap.list_begin(); it != scoreMap.list_end(); ++it)
    {
        printf("  %s: %d\n", it->first.c_str(), it->second);
    }

    // 验证equal_range仍然有效
    auto alice_count = scoreMap.count("Alice");
    auto bob_count = scoreMap.count("Bob");
    EXPECT_EQ(alice_count, 2);
    EXPECT_EQ(bob_count, 2);
    EXPECT_EQ(scoreMap.count("Charlie"), 1);

    printf("MultiMap MoveToListNodeFront test passed\n");
}

/**
 * @brief 测试MultiMap的move_to_list_node_back接口
 */
TEST(NFShmHashMultiMapWithListAdvancedTest, MoveToListNodeBack)
{
    printf("========== MultiMap MoveToListNodeBack Test ==========\n");

    NFShmHashMultiMapWithList<std::string, int, 100> scoreMap;
    scoreMap.CreateInit();

    // 插入多重数据并排序
    scoreMap.insert({"Alice", 85});
    scoreMap.insert({"Alice", 92});
    scoreMap.insert({"Bob", 78});
    scoreMap.insert({"Bob", 89});
    scoreMap.insert({"Charlie", 91});
    scoreMap.sort_list();  // 按value升序排序

    printf("Original sorted order:\n");
    for (auto it = scoreMap.list_begin(); it != scoreMap.list_end(); ++it)
    {
        printf("  %s: %d\n", it->first.c_str(), it->second);
    }

    // 测试1：移动某个Bob记录到后端
    printf("\nTest 1: Move specific Bob record to back\n");
    
    auto bob_range = scoreMap.equal_range("Bob");
    auto target_bob = bob_range.first;  // 指向Bob的第一个记录（78分）
    
    scoreMap.move_to_list_node_back(target_bob);

    printf("After moving Bob's first record to back:\n");
    for (auto it = scoreMap.list_begin(); it != scoreMap.list_end(); ++it)
    {
        printf("  %s: %d\n", it->first.c_str(), it->second);
    }

    // 测试2：使用链表迭代器
    printf("\nTest 2: Move using list_iterator\n");
    
    auto list_it = scoreMap.list_begin();
    ++list_it;  // 指向第二个元素
    scoreMap.move_to_list_node_back(list_it);

    printf("After moving second element to back:\n");
    for (auto it = scoreMap.list_begin(); it != scoreMap.list_end(); ++it)
    {
        printf("  %s: %d\n", it->first.c_str(), it->second);
    }

    // 验证多重映射的键统计
    EXPECT_EQ(scoreMap.count("Alice"), 2);
    EXPECT_EQ(scoreMap.count("Bob"), 2);
    EXPECT_EQ(scoreMap.count("Charlie"), 1);
    EXPECT_EQ(scoreMap.size(), 5);

    printf("MultiMap MoveToListNodeBack test passed\n");
}

/**
 * @brief 综合测试：多重映射特有的场景和性能测试
 */
TEST(NFShmHashMultiMapWithListAdvancedTest, MultiMapSpecificScenarios)
{
    printf("========== MultiMap Specific Scenarios Test ==========\n");

    // 测试1：大量相同键的值的处理
    printf("Test 1: Handle many values for same key\n");
    {
        NFShmHashMultiMapWithList<std::string, int, 100> manyValuesMap;
        manyValuesMap.CreateInit();

        // 为同一个键插入多个值
        std::vector<int> scores = {85, 92, 78, 89, 95, 82, 88, 91, 87, 93};
        
        for (int score : scores)
        {
            manyValuesMap.insert_list_sorted({"Student", score});
        }

        printf("After inserting %d scores for 'Student':\n", (int)scores.size());
        std::vector<int> sorted_scores;
        for (auto it = manyValuesMap.list_begin(); it != manyValuesMap.list_end(); ++it)
        {
            printf("  %s: %d\n", it->first.c_str(), it->second);
            sorted_scores.push_back(it->second);
        }

        // 验证排序正确性
        EXPECT_TRUE(std::is_sorted(sorted_scores.begin(), sorted_scores.end()));
        EXPECT_EQ(manyValuesMap.count("Student"), scores.size());
        EXPECT_EQ(manyValuesMap.size(), scores.size());

        // 验证equal_range覆盖所有值
        auto range = manyValuesMap.equal_range("Student");
        int count = 0;
        for (auto it = range.first; it != range.second; ++it)
        {
            count++;
        }
        EXPECT_EQ(count, scores.size());
    }

    // 测试2：混合操作场景
    printf("\nTest 2: Mixed operations scenario\n");
    {
        NFShmHashMultiMapWithList<int, std::string, 50> mixedMap;
        mixedMap.CreateInit();

        // 使用不同接口插入数据
        mixedMap.insert_list_sorted({1, "zebra"});
        mixedMap.emplace_list_sorted(1, std::string("apple"));
        mixedMap.insert_list_sorted({2, "banana"});
        mixedMap.emplace_hint_list_sorted(1, std::string("cherry"));

        printf("After mixed insertions:\n");
        for (auto it = mixedMap.list_begin(); it != mixedMap.list_end(); ++it)
        {
            printf("  %d: %s\n", it->first, it->second.c_str());
        }

        // 移动操作
        auto it_to_move = mixedMap.find(1);
        mixedMap.move_to_list_sorted(it_to_move);

        printf("\nAfter move operation:\n");
        std::vector<std::string> values;
        for (auto it = mixedMap.list_begin(); it != mixedMap.list_end(); ++it)
        {
            printf("  %d: %s\n", it->first, it->second.c_str());
            values.push_back(it->second);
        }

        // 验证字符串排序
        EXPECT_TRUE(std::is_sorted(values.begin(), values.end()));
        EXPECT_EQ(mixedMap.count(1), 3);
        EXPECT_EQ(mixedMap.count(2), 1);
    }

    // 测试3：性能测试
    printf("\nTest 3: Performance test\n");
    {
        const int TEST_SIZE = 200;
        NFShmHashMultiMapWithList<int, int, TEST_SIZE> perfMap;
        perfMap.CreateInit();

        // 为每个键插入多个值
        std::random_device rd;
        std::mt19937 gen(rd());
        std::uniform_int_distribution<> key_dist(1, 20);  // 20个不同的键
        std::uniform_int_distribution<> value_dist(1, 1000);

        auto start = std::chrono::high_resolution_clock::now();
        for (int i = 0; i < TEST_SIZE; ++i)
        {
            int key = key_dist(gen);
            int value = value_dist(gen);
            perfMap.insert_list_sorted({key, value});
        }
        auto end = std::chrono::high_resolution_clock::now();
        auto insert_time = std::chrono::duration_cast<std::chrono::microseconds>(end - start);

        printf("insert_list_sorted %d elements took %lld microseconds\n", 
               TEST_SIZE, insert_time.count());

        // 验证排序正确性
        std::vector<int> all_values;
        for (auto it = perfMap.list_begin(); it != perfMap.list_end(); ++it)
        {
            all_values.push_back(it->second);
        }
        EXPECT_TRUE(std::is_sorted(all_values.begin(), all_values.end()));
        EXPECT_EQ(perfMap.size(), TEST_SIZE);

        // 测试equal_range性能
        start = std::chrono::high_resolution_clock::now();
        for (int key = 1; key <= 20; ++key)
        {
            auto range = perfMap.equal_range(key);
            int count = 0;
            for (auto it = range.first; it != range.second; ++it)
            {
                count++;
            }
            // 验证count方法与equal_range一致
            EXPECT_EQ(count, perfMap.count(key));
        }
        end = std::chrono::high_resolution_clock::now();
        auto range_time = std::chrono::duration_cast<std::chrono::microseconds>(end - start);

        printf("equal_range for 20 keys took %lld microseconds\n", range_time.count());
    }

    printf("MultiMap Specific Scenarios test passed\n");
}

